package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202410;

public class leetcode20241009 {
    public int minimumDifference(int[] nums,int k){
        /**
         * 找到按位或最接近k的子数组，返回最小的绝对差值
         */
        // 方法一：暴力法，超时
//        int ans=Integer.MAX_VALUE;
//        for(int i=0;i<nums.length;i++){
//            int x=nums[i];
//            ans=Math.min(ans,Math.abs(x-k));
//            for(int j=i-1;j>=0;j--){
//                nums[j]|=x;// 现在 nums[j] = 原数组 nums[j] 到 nums[i] 的 OR
//                ans=Math.min(ans,Math.abs(nums[j]-k));
//            }
//        }
//        return ans;

        // 方法二：滑动窗口
        int ans=Integer.MAX_VALUE;
        int left=0,bottom=0,rightOr=0;
        for(int right=0;right<nums.length;right++){
            rightOr|=nums[right];
            while(left<=right && (nums[left] | rightOr)>k){
                ans=Math.min(ans,nums[left] | rightOr-k);
                if(bottom<=left){
                    // 重新构建一个栈
                    // 由于left即将移出窗口，只需要计算left+1
                    for(int i=right-1;i>left;i--){
                        nums[i]=nums[i+1];
                    }
                    bottom=right;// 重新构建
                    rightOr=0;
                }
                left++;
            }
            if(left<=right){
                ans=Math.min(ans,k-(nums[left] | rightOr));
            }
        }
        return ans;
    }
}
